﻿#include <iostream>
#include <vector>
#include <stack>

// 辅助函数：交换两个元素的值
static void swap(int& a, int& b) {
    const int temp = a;
    a = b;
    b = temp;
}

// 辅助函数：分区操作
static int partition(std::vector<int>& arr, const int low, const int high) {
    const int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1; // 较小元素的索引

    // 参考样例: 3 6 7 2 5, i = -1
    // j = 0: i = 0, 3 6 7 2 5 (3与3交换, 不变)
    // j = 1: i = 0, 3 6 7 2 5
    // j = 2: i = 0, 3 6 7 2 5
    // j = 3: i = 1, 3 2 7 6 5
    for (int j = low; j < high; ++j) {
        if (arr[j] <= pivot) {
            ++i;
            swap(arr[i], arr[j]);
        }
    }

    // for循环之后, i + 1 = 2, 3 2 5 6 7
    swap(arr[i + 1], arr[high]);
    return i + 1;
}
 
// 非递归快速排序函数
static void quickSortIterative(std::vector<int>& arr) {
    std::stack<std::pair<int, int>> stk;
 
    // 初始调用时，将整个数组的范围压入栈中
    stk.emplace(0, arr.size() - 1);
 
    // 当栈不为空时，继续排序
    while (!stk.empty()) {
        // 从栈中弹出当前范围的高位和低位索引
        const auto range = stk.top();
        stk.pop();
        int high = range.second;
        int low = range.first;
 
        // 获取分区索引
        const int pi = partition(arr, low, high);
 
        // 如果分区索引的左侧有元素，则将其范围压入栈中
        if (pi - 1 > low) {
            stk.emplace(low, pi - 1);
        }
 
        // 如果分区索引的右侧有元素，则将其范围压入栈中
        if (pi + 1 < high) {
            stk.emplace(pi + 1, high);
        }
    }
}
 
int main_QuickSortByStack()
{
    std::vector<int> arr = {10, 7, 8, 55, 21, 9, 18, 99, 13, 1, 13, 5};
    int n = arr.size();
 
    std::cout << "Unsorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    
    std::cout << std::endl;
 
    quickSortIterative(arr);
 
    std::cout << "Sorted array: ";
    for (int i = 0; i < n; ++i) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
 
    return 0;
}
